class Node {
    constructor(val) {
        this.val = val
        this.left = null
        this.right = null
    }
}

export class BST {
    constructor() {
        this.root = null
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    add(e) {
        if (this.root === null) {
            this.root = new Node(e)
            this.size++

        } else {
            this._add(this.root, e)

        }
    }

    _add(node, e) {
        if (node === null) {
            this.size++
            return new Node(e)
        }

        if (node.val > e) {
            node.left = this._add(node.left, e)

        } else if (node.val < e) {
            node.right = this._add(node.right, e)

        }

        return node
    }

    contains(e) {
        return this._contains(this.root, e)
    }

    _contains(node, e) {
        if (node === null) {
            return false
        }

        if (node.val === e) {
            return true

        } else if (node.val > e) {
            return this._contains(node.left, e)

        } else {
            return this._contains(node.right, e)
        }

    }

    // 前序遍历
    preOrder() {
        this._preOrder(this.root)
    }

    _preOrder(node) {
        if (node === null) {
            return
        }

        console.log(node.val)
        this._preOrder(node.left)
        this._preOrder(node.right)
    }

    // 中序遍历，遍历结果按顺序排列
    inOrder() {
        this._inOrder(this.root)
    }

    _inOrder(node) {
        if (node === null) {
            return
        }

        this._preOrder(node.left)
        console.log(node.val)
        this._preOrder(node.right)
    }

    // 后序遍历
    postOrder() {
        this._postOrder(this.root)
    }

    _postOrder(node) {
        if (node === null) {
            return
        }

        this._preOrder(node.left)
        this._preOrder(node.right)
        console.log(node.val)
    }

    preOrderNR() {
        const stack = []
        stack.push(this.root)

        while (stack.length > 0) {
            const n = stack.pop()

            console.log(n.val)
            n.right && stack.push(n.right)
            n.left && stack.push(n.left)
        }
    }

    levelOrder() {
        const queue = []
        queue.push(this.root)

        while (queue.length > 0) {
            const n = queue.shift()

            console.log(n.val)
            n.right && queue.push(n.right)
            n.left && queue.push(n.left)
        }
    }

    minimum() {
        if (this.size === 0) {
            throw new Error('BST is empty.')
        }

        return this._minimum(this.root).val
    }

    _minimum(node) {
        if (node.left === null) {
            return node
        }

        return this._minimum(node.left)
    }

    maximum() {
        if (this.size === 0) {
            throw new Error('BST is empty.')
        }

        return this._maximum(this.root).val
    }

    _maximum(node) {
        if (node.right === null) {
            return node
        }

        return this._maximum(node.right)
    }

    removeMin() {
        const min = this.minimum()
        this.root = this._removeMin(this.root)
        return min
    }

    _removeMin(node) {
        if (node.left === null) {
            const rightNode = node.right
            node.right = null
            this.size--
            return rightNode
        }

        node.left = this._removeMin(node.left)
        return node
    }

    removeMax() {
        const max = this.maximum()
        this.root = this._removeMax(this.root)
        return max
    }

    _removeMax(node) {
        if (node.right === null) {
            const leftNode = node.left
            node.left = null
            this.size--
            return leftNode
        }

        node.right = this._removeMax(node.right)
        return node
    }

    remove(e) {
        this.root = this._remove(this.root, e)
    }

    _remove(node, e) {
        if (node === null) {
            return null
        }

        if (e < node.val) {
            node.left = this._remove(node.left, e)
            return node

        } else if (e > node.val) {
            node.right = this._remove(node.right, e)
            return node

        } else if (e === node.val) {

            if (node.left === null) {
                const rightNode = node.right
                node.right = null
                this.size--
                return rightNode
            }

            if (node.right === null) {
                const leftNode = node.left
                node.left = null
                this.size--
                return leftNode
            }

            // 待删除节点左右子树均不为空的情况
            // 找到比删除节点大的最小节点，即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            const successor = this._minimum(node.right)
            successor.right = this._removeMin(node.right)
            successor.left = node.left

            node.left = node.right = null
            return successor
        }

    }

}


/*
__add(node, e) {
    if (node.val === e) {
        return

    } else if (node.val < e && node.left === null) {
        node.left = new Node(e)
        this.size++
        return

    } else if (node.val > e && node.right === null) {
        node.right = new Node(e)
        this.size++
        return

    }

    if (node.val < e) {
        this.__add(node.left, e)

    } else {
        this.__add(node.right, e)

    }
}
*/